package cn.bouncyslime.algorithms.tree.binaryTree;

import java.util.*;

public class Traversal_levelOrder_2 {
    public List<List<Integer>> levelOrder(TreeNode root){
        if (root==null){
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while (count>0){
                TreeNode node = ((LinkedList<TreeNode>) queue).poll();
                list.add(node.getValue());
                if (node.getLeft()!=null)   queue.offer(node.getLeft());
                if (node.getRight()!=null)  queue.offer(node.getRight());
                count --;
            }
            result.add(list);
        }
//        Collections.reverse(result);
        return reverseList(result);
    }

    // 通过压栈出栈的方式颠倒列表中元素的顺序
    public List<List<Integer>> reverseList(List<List<Integer>> list){
        Deque<List<Integer>> stack = new ArrayDeque<>();
        for (List<Integer> l : list){
            stack.push(l);
        }
        list.clear();
        for (List<Integer> l : stack){
            list.add(l);
        }
        return list;
    }

    public static void main(String[] args){
        BinaryTree bt = new BinaryTree();
        int[] array = {1,2,3,4,5,0,0,0,0,6,7};
//        int[] array = {};
        TreeNode root = bt.createTree(array);

        Traversal_levelOrder_2 tl = new Traversal_levelOrder_2();
        List<List<Integer>> list = tl.levelOrder(root);
        for (List<Integer> l : list){
            for (Integer i : l){
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}
